from typing import List

# 贪心
# 通过维护当前能到达的最远位置和下一步能到达的最远位置，来选择跳跃点。
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        # 需要跳跃的次数
        jumps = 0
        # 当前能到达的最远位置
        current_end = 0
        # 下一步能到达的最远位置
        farthest = 0
        for i in range(n):
            farthest = max(farthest, i + nums[i])
            if farthest >= n - 1:
                return jumps + 1
            # 当遍历到current_end时，表示需要进行一次跳跃
            if i == current_end:
                jumps += 1
                # 将current_end更新为farthest（新的跳跃范围）
                current_end = farthest
        return jumps